ass Solution {
public:
    bool isUnique(string astr) 
    {
        //利用鸽巢原理做优化
        if(astr.size()>26) return false;

        int bitMap=0;
        for(char e:astr)
        {
            int i=e-'a';
            //if(((1<<i)&bitMap)==1) return false; 注意！这是错误的
            if(((bitMap>>i)&1)==1) return false;
            else bitMap|= 1<<i;
        }
        return true;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int ret=0;
        for(auto e:nums) ret^=e;
        for(int i=0;i<=nums.size();i++) ret^=i;
        return ret;
    }
};

class Solution {
public:
    int getSum(int a, int b) 
    {
        while(b!=0)
        {
            int x = a^b;
            unsigned int carry = (unsigned int)(a&b)<<1; 
            //-1的话因为全部是1，是未定义行为，所以把-1当成无符号整数
            a=x;
            b=carry;
        }
        return a;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret=0;
        for(int i=0;i<32;i++)//依次去修改ret的每一位
        {
            int sum=0;
            for(int e:nums)//计算nums中所有的数的第i位的和
                if(((e>>i)&1)==1)
                sum++;
            if(sum%3==1)
                ret |= (1<<i);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        //1. 将所有的数异或在一起
        int tmp = 0;
        for(auto x:nums) tmp^=x;
        for(int i=1;i<=nums.size()+2;i++) tmp^=i;
        //2. 找出a，b中比特位不同的那一位
        int diff=0;
        while(1)
        {
            if(((tmp>>diff)&1)==1) break;
            else diff++;
        }
        //3. 根据diff位的不同，将所有的数划分为两类来异或
        int a=0,b=0;
        for(int x:nums)
            if(((x>>diff)&1)==1) b^=x;
            else a^=x;
        for(int i=1;i<=nums.size()+2;i++)
            if(((i>>diff)&1)==1) b^=i;
            else a^=i;
        return {a,b};
    }
};

